package dp;

/**
 * 背包问题
 *
 * @author chenyang
 */
public class KnapsnackDP {

    public static int maxWeight(int[] w, int[] v, int weight) {
        if (weight == 0) {
            return 0;
        }
        int[][] c = new int[w.length + 1][weight + 1];

        for (int i = 1; i <= weight; i++) {
            for (int j = 1; j <= w.length; j++) {
                if (i < w[j - 1]) {
                    c[j][i] = c[j - 1][i];
                } else {
                    c[j][i] = Math.max(c[j - 1][i], v[j - 1] + c[j - 1][i - w[j - 1]]);
                }
            }
        }
        return c[w.length][weight];
    }
}
